home *** CD-ROM | disk | FTP | other *** search
/ IRIX Base Documentation 2002 November / SGI IRIX Base Documentation 2002 November.iso / usr / share / catman / p_man / cat3c / tsearch.z / tsearch
Encoding:
Text File  |  2002-10-03  |  11.0 KB  |  265 lines
  1.  
  2.  
  3.  
  4. TTTTSSSSEEEEAAAARRRRCCCCHHHH((((3333CCCC))))                                                        TTTTSSSSEEEEAAAARRRRCCCCHHHH((((3333CCCC))))
  5.  
  6.  
  7.  
  8. NNNNAAAAMMMMEEEE
  9.      tsearch, tfind, tdelete, twalk - manage binary search trees
  10.  
  11. SSSSYYYYNNNNOOOOPPPPSSSSIIIISSSS
  12.      ####iiiinnnncccclllluuuuddddeeee <<<<sssseeeeaaaarrrrcccchhhh....hhhh>>>>
  13.  
  14.      vvvvooooiiiidddd ****ttttsssseeeeaaaarrrrcccchhhh ((((ccccoooonnnnsssstttt vvvvooooiiiidddd ****kkkkeeeeyyyy,,,, vvvvooooiiiidddd ********rrrroooooooottttpppp,,,,
  15.                     iiiinnnntttt ((((****ccccoooommmmppppaaaarrrr))))((((ccccoooonnnnsssstttt vvvvooooiiiidddd ****,,,, ccccoooonnnnsssstttt vvvvooooiiiidddd ****))))))));;;;
  16.  
  17.      vvvvooooiiiidddd ****ttttffffiiiinnnndddd ((((ccccoooonnnnsssstttt vvvvooooiiiidddd ****kkkkeeeeyyyy,,,, vvvvooooiiiidddd **** ccccoooonnnnsssstttt ****rrrroooooooottttpppp,,,,
  18.                   iiiinnnntttt ((((****ccccoooommmmppppaaaarrrr))))((((ccccoooonnnnsssstttt vvvvooooiiiidddd ****,,,, ccccoooonnnnsssstttt vvvvooooiiiidddd ****))))))));;;;
  19.  
  20.      vvvvooooiiiidddd ****ttttddddeeeelllleeeetttteeee ((((ccccoooonnnnsssstttt vvvvooooiiiidddd ****kkkkeeeeyyyy,,,, vvvvooooiiiidddd ********rrrroooooooottttpppp,,,,
  21.                     iiiinnnntttt ((((****ccccoooommmmppppaaaarrrr))))((((ccccoooonnnnsssstttt vvvvooooiiiidddd ****,,,, ccccoooonnnnsssstttt vvvvooooiiiidddd ****))))))));;;;
  22.  
  23.      vvvvooooiiiidddd ttttwwwwaaaallllkkkk ((((((((ccccoooonnnnsssstttt vvvvooooiiiidddd ****rrrrooooooootttt,,,, vvvvooooiiiidddd ccccoooonnnnsssstttt ((((****aaaaccccttttiiiioooonnnn))))((((vvvvooooiiiidddd ****,,,, VVVVIIIISSSSIIIITTTT,,,, iiiinnnntttt))))))));;;;
  24.  
  25. DDDDEEEESSSSCCCCRRRRIIIIPPPPTTTTIIIIOOOONNNN
  26.      _t_s_e_a_r_c_h, _t_f_i_n_d, _t_d_e_l_e_t_e, and _t_w_a_l_k are routines for manipulating binary
  27.      search trees.  They are generalized from Knuth (6.2.2) Algorithms T and
  28.      D.  All comparisons are done with a user-supplied routine.  This routine
  29.      is called with two arguments, the pointers to the elements being
  30.      compared.  It returns an integer less than, equal to, or greater than 0,
  31.      according to whether the first argument is to be considered less than,
  32.      equal to or greater than the second argument.  The comparison function
  33.      need not compare every byte, so arbitrary data may be contained in the
  34.      elements in addition to the values being compared.
  35.  
  36.      _t_s_e_a_r_c_h is used to build and access the tree.  KKKKeeeeyyyy is a pointer to a
  37.      datum to be accessed or stored.  If there is a datum in the tree equal to
  38.      *key (the value pointed to by key), a pointer to this found datum is
  39.      returned.  Otherwise, *key is inserted, and a pointer to it returned.
  40.      Only pointers are copied, so the calling routine must store the data.
  41.      RRRRoooooooottttpppp points to a variable that points to the root of the tree.  A NULL
  42.      value for the variable pointed to by rrrroooooooottttpppp denotes an empty tree; in this
  43.      case, the variable will be set to point to the datum which will be at the
  44.      root of the new tree.
  45.  
  46.      Like _t_s_e_a_r_c_h, _t_f_i_n_d will search for a datum in the tree, returning a
  47.      pointer to it if found.  However, if it is not found, _t_f_i_n_d will return a
  48.      NULL pointer.  The arguments for _t_f_i_n_d are the same as for _t_s_e_a_r_c_h.
  49.  
  50.      _T_d_e_l_e_t_e deletes a node from a binary search tree.  The arguments are the
  51.      same as for _t_s_e_a_r_c_h.  The variable pointed to by rrrroooooooottttpppp will be changed if
  52.      the deleted node was the root of the tree.  _T_d_e_l_e_t_e returns a pointer to
  53.      the parent of the deleted node, or a NULL pointer if the node is not
  54.      found.
  55.  
  56.      _T_w_a_l_k traverses a binary search tree.  RRRRooooooootttt is the root of the tree to be
  57.      traversed.  (Any node in a tree may be used as the root for a walk below
  58.      that node.)  _A_c_t_i_o_n is the name of a routine to be invoked at each node.
  59.      This routine is, in turn, called with three arguments.  The first
  60.  
  61.  
  62.  
  63.                                                                         PPPPaaaaggggeeee 1111
  64.  
  65.  
  66.  
  67.  
  68.  
  69.  
  70. TTTTSSSSEEEEAAAARRRRCCCCHHHH((((3333CCCC))))                                                        TTTTSSSSEEEEAAAARRRRCCCCHHHH((((3333CCCC))))
  71.  
  72.  
  73.  
  74.      argument is the address of the node being visited.  The second argument
  75.      is a value from an enumeration data type _t_y_p_e_d_e_f _e_n_u_m { _p_r_e_o_r_d_e_r,
  76.      _p_o_s_t_o_r_d_e_r, _e_n_d_o_r_d_e_r, _l_e_a_f } _V_I_S_I_T; (defined in the <_s_e_a_r_c_h._h> header
  77.      file), depending on whether this is the first, second or third time that
  78.      the node has been visited (during a depth-first, left-to-right traversal
  79.      of the tree), or whether the node is a leaf.  The third argument is the
  80.      level of the node in the tree, with the root being level zero.
  81.  
  82.      The pointers to the key and the root of the tree should be of type
  83.      pointer-to-element, and cast to type pointer-to-character.  Similarly,
  84.      although declared as type pointer-to-character, the value returned should
  85.      be cast into type pointer-to-element.
  86.  
  87. EEEEXXXXAAAAMMMMPPPPLLLLEEEE
  88.      The following code reads in strings and stores structures containing a
  89.      pointer to each string and a count of its length.  It then walks the
  90.      tree, printing out the stored strings and their lengths in alphabetical
  91.      order.
  92.  
  93.           #include <search.h>
  94.           #include <stdio.h>
  95.  
  96.           struct node {       /* pointers to these are stored in the tree */
  97.                char *string;
  98.                int length;
  99.           };
  100.           char string_space[10000];     /* space to store strings */
  101.           struct node nodes[500];  /* nodes to store */
  102.           struct node *root = NULL;     /* this points to the root */
  103.  
  104.           main( )
  105.           {
  106.                char *strptr = string_space;
  107.                struct node *nodeptr = nodes;
  108.                void print_node( ), twalk( );
  109.                int i = 0, node_compare( );
  110.  
  111.                while (gets(strptr) != NULL && i++ < 500)  {
  112.                     /* set node */
  113.                     nodeptr->string = strptr;
  114.                     nodeptr->length = strlen(strptr);
  115.                     /* put node into the tree */
  116.                     (void) tsearch((char *)nodeptr, (char **) &root,
  117.                            node_compare);
  118.                     /* adjust pointers, so we don't overwrite tree */
  119.                     strptr += nodeptr->length + 1;
  120.                     nodeptr++;
  121.                }
  122.                twalk((char *)root, print_node);
  123.           }
  124.           /*
  125.                This routine compares two nodes, based on an
  126.  
  127.  
  128.  
  129.                                                                         PPPPaaaaggggeeee 2222
  130.  
  131.  
  132.  
  133.  
  134.  
  135.  
  136. TTTTSSSSEEEEAAAARRRRCCCCHHHH((((3333CCCC))))                                                        TTTTSSSSEEEEAAAARRRRCCCCHHHH((((3333CCCC))))
  137.  
  138.  
  139.  
  140.               alphabetical ordering of the string field.
  141.           */
  142.           int
  143.           node_compare(node1, node2)
  144.           char *node1, *node2;
  145.           {
  146.                return strcmp(((struct node *)node1)->string,
  147.                ((struct node *) node2)->string);
  148.           }
  149.           /*
  150.                This routine prints out a node, the first time
  151.                twalk encounters it.
  152.           */
  153.           void
  154.           print_node(node, order, level)
  155.           char **node;
  156.           VISIT order;
  157.           int level;
  158.           {
  159.                if (order == postorder || order == leaf)  {
  160.                     (void)printf("string = %20s,  length = %d\n",
  161.                                   (*((struct node **)node))->string,
  162.                                   (*((struct node **)node))->length);
  163.                }
  164.           }
  165.  
  166. SSSSEEEEEEEE AAAALLLLSSSSOOOO
  167.      bsearch(3C), hsearch(3C), lsearch(3C).
  168.  
  169. DDDDIIIIAAAAGGGGNNNNOOOOSSSSTTTTIIIICCCCSSSS
  170.      A NULL pointer is returned by _t_s_e_a_r_c_h if there is not enough space
  171.      available to create a new node.
  172.      A NULL pointer is returned by _t_f_i_n_d and _t_d_e_l_e_t_e if rrrroooooooottttpppp is NULL on
  173.      entry.
  174.      If the datum is found, both _t_s_e_a_r_c_h and _t_f_i_n_d return a pointer to it.  If
  175.      not, _t_f_i_n_d returns NULL, and _t_s_e_a_r_c_h returns a pointer to the inserted
  176.      item.
  177.  
  178. WWWWAAAARRRRNNNNIIIINNNNGGGGSSSS
  179.      The rrrrooooooootttt argument to _t_w_a_l_k is one level of indirection less than the
  180.      rrrroooooooottttpppp arguments to _t_s_e_a_r_c_h and _t_d_e_l_e_t_e.
  181.      There are two nomenclatures used to refer to the order in which tree
  182.      nodes are visited.  _t_s_e_a_r_c_h uses preorder, postorder and endorder to
  183.      respectively refer to visiting a node before any of its children, after
  184.      its left child and before its right, and after both its children.  The
  185.      alternate nomenclature uses preorder, inorder and postorder to refer to
  186.      the same visits, which could result in some confusion over the meaning of
  187.      postorder.
  188.  
  189.  
  190.  
  191.  
  192.  
  193.  
  194.  
  195.                                                                         PPPPaaaaggggeeee 3333
  196.  
  197.  
  198.  
  199.  
  200.  
  201.  
  202. TTTTSSSSEEEEAAAARRRRCCCCHHHH((((3333CCCC))))                                                        TTTTSSSSEEEEAAAARRRRCCCCHHHH((((3333CCCC))))
  203.  
  204.  
  205.  
  206. CAVEAT
  207.      If the calling function alters the pointer to the root, results are
  208.      unpredictable.
  209.  
  210.  
  211.  
  212.  
  213.  
  214.  
  215.  
  216.  
  217.  
  218.  
  219.  
  220.  
  221.  
  222.  
  223.  
  224.  
  225.  
  226.  
  227.  
  228.  
  229.  
  230.  
  231.  
  232.  
  233.  
  234.  
  235.  
  236.  
  237.  
  238.  
  239.  
  240.  
  241.  
  242.  
  243.  
  244.  
  245.  
  246.  
  247.  
  248.  
  249.  
  250.  
  251.  
  252.  
  253.  
  254.  
  255.  
  256.  
  257.  
  258.  
  259.  
  260.  
  261.                                                                         PPPPaaaaggggeeee 4444
  262.  
  263.  
  264.  
  265.